package com.kelvin.oocl.crms.util;

/**
 * 实现双向链表
 * @author MAIKE
 *
 */
public class DoubleLinkList {
	
	
	public static void main(String[] args) throws Exception {
		int[] n = {6,3,5,9,2,10,8,1,12,7};
		DoubleLinkList linkList = new DoubleLinkList(n);
//		linkList.printFromHead();
//		linkList.printFromTail();
//		System.out.println(linkList.getNodeCounts());
		
		
//		boolean flag = linkList.insertNode(linkList.new Node(12));
//		boolean flag = linkList.insertNode(linkList.new Node(12), 1);
//		DoubleLinkList linkList = new DoubleLinkList();
//		boolean flag = linkList.deleteNode(linkList.new Node(12));
//		System.out.println(flag);
		
		System.out.println(linkList.getNode(9).getValue());
		
		linkList.sortList(linkList);
		linkList.printFromHead();
		System.out.println();
		linkList.printFromTail();
		System.out.println();
		System.out.println(linkList.getNodeCounts());
		System.out.println("********");
		
		int index = linkList.binarySearch(linkList.new Node(10), linkList);
		System.out.println("index==>"+index);
	}
	
	private Node head = null;	//头节点
	private Node tail = null;	//尾节点
	private int nodeCounts;
	
	public DoubleLinkList() {
	}
	
	public DoubleLinkList(int[] values) {
		if(values.length>0){
			Node firstNode = new Node(values[0]);
			nodeCounts++;
			this.head = firstNode;
			int i=1;
			Node currNode = firstNode;
			Node nextNode= null;
			while(i<values.length){
				nextNode = new Node(values[i]);
				nodeCounts++;
				nextNode.setPreNode(currNode);
				currNode.setNextNode(nextNode);
				currNode = nextNode;
				i++;
			}
			tail = currNode;
		}
	}
	
	/**
	 * 二分查找
	 * @param node
	 * @param sortedList
	 */
	public int binarySearch(Node node,DoubleLinkList sortedList){
		if(node == null || sortedList==null){
			return -1;
		}
		int low = 0;
		int high = sortedList.getNodeCounts()-1;
		int middle=0;
		while(low<=high){
			middle = (low+high)/2;
			if(node.getValue()==this.getValueByIndex(middle, sortedList)){
				return middle;
			}else if(node.getValue()<this.getValueByIndex(middle, sortedList)){
				high = --middle;
			}else {
				low = ++middle;
			}
		}
		
		return middle;
	}
	
	private int getValueByIndex(int index,DoubleLinkList sortedList){
		if(sortedList==null){
			return -1;
		}
		int i = 0;
		Node currNode = sortedList.getHead();
		while(currNode!=null){
			if(i==index){
				return currNode.getValue();
			}
			i++;
			currNode = currNode.getNextNode();
		}
		return -1;
	}
	
	/**
	 * 根据下标获取节点
	 * @param index
	 * @return
	 * @throws Exception
	 */
	public Node getNode(int index) throws Exception{
		if(index<0){
			return null;
		}
		if(this.head==null){
			throw new Exception("The List is empty");
		}
		if(index+1>this.getNodeCounts()){
			throw new Exception("The index is out of linkLisk's length");
		}
		Node node = this.head;
		int i=0;
		while(node!=null){
			if(i==index){
				return node;
			}
			i++;
			node = node.getNextNode();
		}
		return null;
	}
	
	/**
	 * 对链表进行排序
	 * @param linkList
	 */
	public void sortList(DoubleLinkList linkList){
		if(null==linkList){
			return;
		}
		if(linkList.getNodeCounts()<=1){
			return;
		}
		Node currNode = linkList.getHead();
		Node cNode = null;
		int min = 0;
		Node minNode;
		while(currNode!=null){
			cNode = currNode.getNextNode();
			min = currNode.getValue();
			minNode = currNode;
			while(cNode!=null){
				if(cNode.getValue()<min){
					min = cNode.getValue();
					minNode = cNode;
				}
				cNode = cNode.getNextNode();
			}
			if(!minNode.equals(currNode)){
				int temp = minNode.getValue();
				minNode.setValue(currNode.getValue());
				currNode.setValue(temp);
			}
			currNode = currNode.getNextNode();
		}
	}
	
	/**
	 * 删除某一个节点
	 * @param node
	 */
	public boolean deleteNode(Node node) throws Exception{
		if(node==null){
			return false;
		}
		if(this.head==null){
			throw new Exception("The doubleLinkList is empty!");
		}
		Node cuNode = head;
		while(cuNode!=null){
			if(cuNode.equals(node)){
				Node nextNode = cuNode.getNextNode();
				Node preNode = cuNode.getPreNode();
				if(nextNode==null){
					this.tail = preNode;
					if(preNode==null){
						this.head = nextNode;
					}else {
						preNode.setNextNode(null);
					}
				}else if(preNode == null){
					this.head = nextNode;
					nextNode.setPreNode(null);
				}else {
					nextNode.setPreNode(preNode);
					preNode.setNextNode(nextNode);
				}
				nodeCounts--;
				return true;
			}
			cuNode = cuNode.getNextNode();
		}
		
		return false;
	}
	
	/**
	 * 从链表末尾插入
	 * @param node
	 */
	public boolean insertNode(Node node){
		if(null==node){
			return false;
		}
		if(tail==null){
			this.head = node;
			this.tail = node;
			nodeCounts++;
		}else {
			tail.setNextNode(node);
			node.setPreNode(tail);
			this.tail = node;
			nodeCounts++;
		}
		return true;
	}
	
	/**
	 * 将节点插入到指定位置
	 * @param node
	 * @param position begin from 1
	 */
	public boolean insertNode(Node node,int position) throws Exception{
		if(null==node){
			return false;
		}
		if(position<1){
			throw new Exception("position must be grater than 1");
		}else if(position>this.nodeCounts){
			return this.insertNode(node);
		}else if(position==1){
			this.head.setPreNode(node);
			node.setNextNode(this.head);
			this.head = node;
			nodeCounts++;
			return true;
		}else {
			int index = 1;
			Node cuNode = head;
			while(cuNode!=null){
				if(index==position){
					Node preNode = cuNode.getPreNode();
					cuNode.setPreNode(node);
					node.setNextNode(cuNode);
					preNode.setNextNode(node);
					node.setPreNode(preNode);
					nodeCounts++;
					return true;
				}
				index++;
				cuNode = cuNode.getNextNode();
			}
			return false;
		}
	}
	
	/**
	 * 从头开始打印链表节点
	 */
	public void printFromHead(){
		if(this.head==null){
			return;
		}
		Node currNode = head;
		while(currNode != null){
			System.out.print(currNode.getValue()+" ");
			currNode = currNode.getNextNode();
		}
	}
	
	/**
	 * 从尾开始打印链表节点
	 */
	public void printFromTail(){
		if(this.tail==null){
			return;
		}
		Node currNode = tail;
		while(currNode != null){
			System.out.print(currNode.getValue()+" ");
			currNode = currNode.getPreNode();
		}
	}
	
	public int getNodeCounts() {
		return nodeCounts;
	}

	public Node getHead() {
		return head;
	}

	public Node getTail() {
		return tail;
	}

	/*
	 * 链表节点
	 */
	class Node {
		int value;
		Node preNode;
		Node nextNode;
		
		public Node() {
		}
		
		public Node(int value) {
			this.value = value;
		}

		public Node getPreNode() {
			return preNode;
		}

		public void setPreNode(Node preNode) {
			this.preNode = preNode;
		}

		public Node getNextNode() {
			return nextNode;
		}

		public void setNextNode(Node nextNode) {
			this.nextNode = nextNode;
		}

		public int getValue() {
			return value;
		}
		
		public void setValue(int value) {
			this.value = value;
		}

		@Override
		public int hashCode() {
			final int prime = 31;
			int result = 1;
			result = prime * result + getOuterType().hashCode();
			result = prime * result + value;
			return result;
		}

		@Override
		public boolean equals(Object obj) {
			if (this == obj)
				return true;
			if (obj == null)
				return false;
			if (getClass() != obj.getClass())
				return false;
			Node other = (Node) obj;
			if (!getOuterType().equals(other.getOuterType()))
				return false;
			if (value != other.value)
				return false;
			return true;
		}

		private DoubleLinkList getOuterType() {
			return DoubleLinkList.this;
		}
	}
}
